Packet-based communication systems such as those based on Ethernet standards and others include switches, which can be both hardware and software based, but usually are a mixture of hardware and software processing, and which may perform switching based on either ‘layer 2’ (media access control) addresses or ‘layer 3’ (network or IP addresses) or both. One example of a network switch which is hardware based and can perform switching on the basis of both layer 2 and layer 3 addresses is described in GB patent 2337674.
In physical terms, network switches may take a variety of forms. A specific example described herein comprises a modular form wherein the modules are each constituted by an application-specific-integrated circuit coupled to respective ports and each having interfaces for high speed multiple bit parallel links between the modules. However, although implementation of switches as application-specific-integrated circuits containing most of the processing blocks and at least some of the memory required to provide storage of packets is now commonplace, the invention is not intended to be limited to any specific physical implementation.
Whatever may be the specific physical realization, network switches of this general kind typically perform the same basic switching process. They include a database, sometimes called a forwarding database or look-up database, which is accessed in response to address data (typically a destination address in the header of a packet) in order to retrieve ‘associated’ or ‘forwarding’ data which identifies for any given packet the port or ports to which the packet (or a copy thereof) is to be forwarded. For this purpose it is customary when the packet is received to place it in temporary storage (such as a FIFO defined in some respective memory space) while the header including the address data of the packet is subjected to the look-up process.
Look-up databases can be organised in a variety of different ways. Some databases employ hashing on address data or selected parts of it to provide access to entries which include pointers to the respective associated data. If hashing is employed then it is necessary to compare an identified entry with the original address data to ensure that there is a match. Methods exist for providing linked lists in hash controlled look-up databases to cope with the phenomenon that different addresses may hash to the same word value. Other forms of look-up database include a trie database which operates on segments of a key (consisting of all or part of the address data of the packet) and at each stage of the search there is a pointer to a block of entries which are distinguished by the next section of the key and so on. At any stage of the trie search the search may terminate with a pointer to the required associated data. Trie searches are fully described in European patent application No. EP-0551243-A2, U.S. Pat. No. 6,041,053 and more recently in GB patent application No. 0026264 2. Other forms of database employ binary tree searching or combinations of different search facilities, such as for example a cache memory for frequently occurring addresses as well as a trie search facility, as described in GB patent application No. 0025507 5.
Whatever the specific form of look-up, the search will normally produce forwarding data, typically in the form of a port bitmask wherein each for each bit that is set in the bitmask the relevant port must receive a copy of the packet. The search may use either the ‘layer 2’ (media access control) or ‘layer 3’ (network protocol) information in the packet and may also use VLAN identification information. Normally, in addition to the address and other information employed for the look-up, the look-up engine is provided with a status word may indicate the result of some processing done on the packet before it arrives at the look-up engine. The look-up engine may modify the status word to provide information to the transmit side, that is to say that part of the switch which is responsible for forwarding a packet from the ‘transmit’ port or ports. The status word may be modified so as, for example, to flag a change to the media access control destination address, to cause re-calculation of the check sum or cyclic redundancy code and so on. After the search is performed the look-up engine may drive the bitmask through what is termed ‘post-processing logic’. This is provided in modern switches in order to cope with the complexity of trunking (wherein a switch or a stack of switches is connected to another switch or stack of switches by means of a multiplicity of links) special rules relating to cascade connections, namely the means of conveying packets from one unit to another in a stack of units managed as a single entity, various discarding rules and so on. The result of post processing is to produce a modified version of the port bitmask which is then passed on to a control, usually called a receive link table, which controls the passage of the packet to the required destination port or ports after a check is made that there are no other links from a source port in the switch to the required destination port. A receive link table may set up several links from the different source ports simultaneously.
At a ‘transmit’ side of the switch, a packet may again be written into a FIFO store. When the packet reaches its turn for reading out, the status word is examined and any port of which a bit is set in the destination port bitmask must receive a copy of the packet.